package LeetCode;

import java.util.*;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}16:50
 */
public class E16 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x;
        }
    }
    public static void main(String[] args) {

    }

    public List<List<Integer>> levelOrder(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList();
        Stack<Integer> stack = new Stack<>();
        List<List<Integer>> list1s = new ArrayList<>();
        if (root == null){
            return list1s;
        }
        ((LinkedList<TreeNode>) queue).add(root);
        int j = 0;
        while (!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {//queue size就相当于当前层的节点个数  也就是说每个大的循环就是一层
                TreeNode treeNode = queue.poll();
                list.add(treeNode.val);
                if (treeNode.left!=null)
                    ((LinkedList<TreeNode>) queue).add(treeNode.left);
                if (treeNode.right!=null){
                    ((LinkedList<TreeNode>) queue).add(treeNode.right);
                }
            }
            if (j%2!=0){
                for (int i : list){
                    stack.push(i);
                }
                list.clear();
                while (stack.size()!=0){
                    list.add(stack.pop());
                }
            }
            j++;
            list1s.add(list);
        }
        return list1s;
    }
}
